Symmetry is the key difference in storage.

  • Undirected graphs represent a two-way relationship. If there's an edge between A and B, you can go from A to B and from B to A. This means representations must be symmetric.
  • In an adjacency list, if B is in A's list, A must be in B's. In an adjacency matrix `M`, `M[A][B]` must equal `M[B][A]`.
  • Directed graphs (digraphs) represent a one-way relationship. An edge from A to B does not imply an edge from B to A.
  • This asymmetry means we only store the explicit connections. B might be in A's adjacency list, but A will not be in B's unless a specific B->A edge exists.